package org.example.graph_theory;

import java.util.Arrays;
import java.util.LinkedList;

public class Number_of_islands {

    public static void main(String[] args) {
        //岛屿数量

        //给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
        //岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
        //此外，你可以假设该网格的四条边均被水包围。

        char[][] grid = {
                {'1','1','1','1','0'},
                {'1','1','0','1','0'},
                {'1','1','0','0','0'},
                {'0','0','0','0','0'}
        };
//        char[][] grid = {
//                {'1','1','0','0','0'},
//                {'1','1','0','0','0'},
//                {'0','0','1','0','0'},
//                {'0','0','0','1','1'}
//        };

        int s = numIslands(grid);
        System.out.println(s);
    }
    public static int numIslands(char[][] grid) {
        int num = 0;
        LinkedList<int[]> list = new LinkedList<int[]>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1'){
                    num++;
                    grid[i][j] = '0';
                    list.add(new int[]{i,j});
                    bfs(grid,list);
//                    dfs(grid,i,j);
                }
            }
        }
        return num;
    }

    //广度优先遍历
    public static void bfs(char[][] grid,LinkedList<int[]> list){
         while(!list.isEmpty()){
             int[] node = list.removeFirst();
             if (node[0]-1 >= 0 && node[0]-1 < grid.length && grid[node[0]-1][node[1]] == '1'){
                 grid[node[0]-1][node[1]] = '0';
                 list.add(new int[]{node[0]-1,node[1]});
             }
             if (node[0]+1 >= 0 && node[0]+1 < grid.length && grid[node[0]+1][node[1]] == '1'){
                 grid[node[0]+1][node[1]] = '0';
                 list.add(new int[]{node[0]+1,node[1]});
             }
             if (node[1]-1 >= 0 && node[1]-1 < grid[node[0]].length && grid[node[0]][node[1]-1] == '1'){
                 grid[node[0]][node[1]-1] = '0';
                 list.add(new int[]{node[0],node[1]-1});
             }
             if (node[1]+1 >= 0 && node[1]+1 < grid[node[0]].length && grid[node[0]][node[1]+1] == '1'){
                 grid[node[0]][node[1]+1] = '0';
                 list.add(new int[]{node[0],node[1]+1});
             }


         }
    }

    //深度优先遍历算法
    public static void dfs(char[][] grid,int i,int j){
        if (i<0 || i> grid.length-1 || j<0 || j>grid[i].length-1 || grid[i][j] == '0') return;
        grid[i][j] = '0';
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
    }
}
